#include <stdio.h>
#include <stdbool.h> // 为了使用 bool, true, false
#include <limits.h>  // 为了使用 INT_MAX 代表无穷大

// 定义图中节点的数量
#define V 9

// 功能：找到 dist 数组中未被访问过且距离最小的节点的索引
int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++) {
        if (visited[v] == false && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

// 功能：打印最终计算出的最短路径
void printSolution(int dist[], int n) {
    printf("节点 \t 距离源点的距离\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t %d\n", i, dist[i]);
    }
}

// 功能：实现 Dijkstra 算法的主函数
// 参数：graph 是邻接矩阵，src 是源节点
void dijkstra(int graph[V][V], int src) {
    int dist[V];     // 输出数组，dist[i] 将保存从 src 到 i 的最短距离
    bool visited[V]; // 如果节点 i 已被处理，则 visited[i] 为 true

    // 1. 初始化所有节点的距离为无穷大，visited 状态为 false
    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    // 源节点到自身的距离永远是 0
    dist[src] = 0;

    // 2. 核心循环：对所有节点进行处理
    for (int count = 0; count < V - 1; count++) {
        // a. 从尚未处理的节点中，选出距离最小的节点 u
        int u = minDistance(dist, visited);

        // b. 将选出的节点 u 标记为已处理
        visited[u] = true;

        // c. 更新 u 的所有邻居节点的距离值
        for (int v = 0; v < V; v++) {
            // 更新条件：
            // 1. 节点 v 必须是未被访问过的
            // 2. 节点 u 和 v 之间必须有边 (graph[u][v] != 0)
            // 3. 从源点经由 u 到达 v 的总距离 (dist[u] + graph[u][v]) 必须小于当前记录的 dist[v]
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 3. 所有节点处理完毕，打印结果
    printSolution(dist, V);
}

// 主驱动函数
int main() {
    /* 创建我们在第三步中定义的那个图 */
    int graph[V][V] = {
        {0, 4, 0, 0, 0, 0, 0, 8, 0},
        {4, 0, 8, 0, 0, 0, 0, 11, 0},
        {0, 8, 0, 7, 0, 4, 0, 0, 2},
        {0, 0, 7, 0, 9, 14, 0, 0, 0},
        {0, 0, 0, 9, 0, 10, 0, 0, 0},
        {0, 0, 4, 14, 10, 0, 2, 0, 0},
        {0, 0, 0, 0, 0, 2, 0, 1, 6},
        {8, 11, 0, 0, 0, 0, 1, 0, 7},
        {0, 0, 2, 0, 0, 0, 6, 7, 0}
    };
    
    // 调用 dijkstra 函数，计算从节点 0 开始的最短路径
    dijkstra(graph, 0);
    printf("hehe\n");
    printf("fenzhihehe\n");
    printf("new hehe\n");

    return 0;
}